Introdução aos Algoritmos Genéticos: Estruturas Canônicas e de Código Real

Algoritmos Genéticos (AGs)são heurísticas de busca global estocásticas inspiradas nos princípios da evolução natural, especificamente na "sobrevivência do mais apto" darwiniana e na recombinação genética.

1. Estruturas de Representação

AGs Canônicos:Utilizam representações binárias ou em código Gray para codificar variáveis de decisão.
AGs de Código Real (AGCRs):Manipulam diretamente vetores de ponto flutuante, geralmente mais eficientes para otimização contínua.

2. O Ciclo Evolutivo

Um processo iterativo de avaliação, seleção e reprodução. Um conceito crítico é a distinção entre o Genótipo (a sequência codificada de bits/cromossomo) e o Fenótipo (o valor da variável de decisão decodificado no espaço real do problema).

A correspondência de uma string binária para um valor real $x \in [a, b]$ é dada por:

$$x = a + \frac{valor\_decimal \times (b - a)}{2^L - 1}$$

Onde $L$ é o comprimento em bits do cromossomo.

Cliffes de Hamming

Cuidado com os Cliffes de Hamming na codificação binária padrão — situações onde números decimais adjacentes (como 7 e 8) têm padrões binários radicalmente diferentes (0111 vs 1000), tornando difícil para o AG realizar buscas localizadas.

Implementação em Python: Decodificação Binária para Real

Questão 1

Por que o código Gray é frequentemente preferido sobre a codificação binária padrão em AGs?

Requer menos memória para armazenar os cromossomos.

Garante que valores adjacentes diferem apenas por um único bit (Propriedade de Adjacência).

Normaliza automaticamente valores entre 0 e 1.

Aumenta naturalmente a taxa de mutação.

Questão 2

Se a probabilidade de mutação (p) for definida muito alta (por exemplo, p = 0,5), qual é o resultado provável?

O algoritmo converge instantaneamente para o ótimo global.

O AG se comporta como uma busca aleatória.

Estudo de Caso: Otimização de Componente de Ponte

Leia o cenário abaixo e responda às perguntas.

Você está otimizando o projeto de um componente de ponte onde a variável de decisão é "Espessura do Material".

A espessura deve estar entre 0,0 mm e 10,23 mm.
Você está usando um AG canônico com uma representação binária de 10 bits bits.

1. Se um indivíduo tem o cromossomo 0000000000, qual é a espessura decodificada?

Resposta: 0,0 mm
A string binária 0000000000 equivale a 0 em decimal. Usando a fórmula $x = a + \frac{decimal \times (b-a)}{2^L - 1}$, obtemos $0,0 + \frac{0 \times (10,23 - 0,0)}{1023} = 0,0$.

2. Calcule a precisão da busca (a menor mudança possível na espessura) para esta configuração de 10 bits.

Resposta: 0,01 mm
A precisão é definida pela faixa dividida pelo valor decimal máximo possível. $\frac{10,23 - 0}{2^{10} - 1} = \frac{10,23}{1023} = 0,01 mm$.

3. Durante a seleção, o Indivíduo A tem aptidão 10 e o Indivíduo B tem aptidão 30. Usando seleção da Roda da Sorte, qual é a probabilidade de B ser escolhido em vez de A?

Resposta: 75%
Aptidão total = $10 + 30 = 40$. Probabilidade de selecionar B = $\frac{30}{40} = 0,75$ ou 75%. (Razão 3:1).